# !/usr/bin/python
# -*- coding: utf-8 -*-
'''
@File    :   12_shellsort.py
@Time    :   2021/04/01 19:39:47
@Author  :   Qingxiang Zhang
@Version :   1.0
@Contact :   344285081@qq.com
@Desc    :   希尔排序
@Software:    Vscode
'''
'''
希尔排序，将序列分组变成gap分组分组排序，变成插入排序
最优时间复杂度：根据步长序列的不同而不同
最坏时间复杂度：O(n2)
稳定性：不稳定
'''

def shell_sort(aList):
    n = len(aList)
    gap = n // 2
    while gap >=1:
    #希尔算法和插入是算法区别就是gap
        for i in range(gap,len(aList)):
            while i>0:
                if aList[i] < aList[i-gap]:
                    aList[i],aList[i-gap] = aList[i-gap],aList[i]
                    i -= gap
                else:
                    break
        gap = gap //2
    return aList

if __name__ =="__main__":
    aList = [0,3,45,9]
    print(shell_sort(aList))
